package codingInterview.leetcode.editor.cn;

//我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 
//
// 
//
// 示例: 
//
// 输入: n = 10
//输出: 12
//解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 
//
// 说明: 
//
// 
// 1 是丑数。 
// n 不超过1690。 
// 
//
// 注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/ 
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 307 👎 0

import java.util.ArrayList;
import java.util.List;

//Java：剑指 Offer 49 - 丑数
public class ChouShuLcof{
    public static void main(String[] args) {
                Solution solution = new ChouShuLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int nthUglyNumber(int n) {
        if(n<=0) return 0;
        int[] ugly = new int[n];
        ugly[0]=1;
        int two =0, three=0, five=0, length=1;
        while (length<n){
            int min = Math.min(ugly[two]*2, Math.min(ugly[three]*3, ugly[five]*5));
            ugly[length++]=min;
            while (ugly[two]*2<=min)
                two++;
            while(ugly[three]*3<=min)
                three++;
            while (ugly[five]*5<=min)
                five++;
        }
        return ugly[n-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
